package com.sjc.algorithm.interview;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 *
 * @author by SangJiacun
 * @Date 2020/5/14 09:13
 */
public class FullPermutation {

    public static void main(String[] args) {
        int[] numbers = {1,2,3,4,5};
        for(int i = 0;i<10;i++){
            numbers = findNeareastNumber(numbers);
            System.out.println(Arrays.toString(numbers));
//            [1, 2, 3, 5, 4]
//            [1, 2, 5, 4, 3]
//            [1, 5, 3, 4, 2]
//            [1, 5, 4, 2, 3]
//            [1, 5, 4, 3, 2]
//            [5, 2, 3, 4, 1]
//            [5, 2, 4, 1, 3]
//            [5, 2, 4, 3, 1]
//            [5, 4, 1, 3, 2]
//            [5, 4, 3, 2, 1]
        }
    }

    /**
     * 12354  ->  12435
     * @param nums
     * @return
     */
    private static int[] findNeareastNumber(int[] nums){
        // 1. 从后往前，找到 nums[i] > nums[i-1], 返回i
        int index = findIndex(nums);

        // 2. 逆序前一位 和 逆序中的大于它的最小值 交换位置
        int[] numsCooy = Arrays.copyOf(nums,nums.length);
        exchange(numsCooy,index);

        // 3. 把原来的逆序区域 变为正序,不是排序
        reverse(numsCooy,index);
        return numsCooy;
    }

    private static int findIndex(int[] nums){
        for(int i=nums.length-1; i>0;i--){
            if(nums[i] > nums[i-1]){
                return i;
            }
        }
        return 0;
    }

    private static int[] exchange(int[] nums, int index){
        int head = nums[index-1];
        for(int i=index;i<nums.length;i++){
            if(nums[i] > head){
                nums[index-1] = nums[i];
                nums[i] = head;
                break;
            }
        }
        return nums;
    }

    private static int[] reverse(int[] nums, int index){
        for(int i=index,j= nums.length-1;i<j;i++,j--){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        return nums;
    }
}
